package com.lw.leetcode.arr;

import java.util.Arrays;

/**
 * 1035. 不相交的线
 *
 * @Author liw
 * @Date 2021/5/21 10:35
 * @Version 1.0
 */
public class MaxUncrossedLines {

    public static void main(String[] args) {
        MaxUncrossedLines test = new MaxUncrossedLines();
//        int[] a = {2,5,1,2,5};
//        int[] b = {10,5,2,1,5,2};
        int[] a = {1,4,2};
        int[] b = {1,2,4};
//        int[] a = {1};
//        int[] b = {1,1,4};
//        int[] a = {1,3,7,1,7,5};
//        int[] b = {1,9,2,5,1};
        int i = test.maxUncrossedLines(a, b);
        System.out.println(i);
    }

    public int maxUncrossedLines2(int[] nums1, int[] nums2) {
        int a = nums1.length + 1;
        int b = nums2.length + 1;
        int[][] arr = new int[a][b];
        for (int i = 1; i < a; i++) {
            for (int j = 1; j < b; j++) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    arr[i][j] = arr[i - 1][j - 1] + 1;
                } else {
                    arr[i][j] = Math.max(Math.max(arr[i - 1][j - 1], arr[i - 1][j]), arr[i][j - 1]);
                }
            }
        }
        return arr[a - 1][b - 1];
    }

    public int maxUncrossedLines(int[] nums1, int[] nums2) {
        int a = nums1.length + 1;
        int b = nums2.length + 1;
        int[] arr = new int[b];
        for (int i = 1; i < a; i++) {
            int item = 0;
            for (int j = 1; j < b; j++) {
                int c = arr[j];
                if (nums1[i - 1] == nums2[j - 1]) {
                    arr[j] = item + 1;
                } else {
                    arr[j] = Math.max(arr[j], arr[j - 1]);
                }
                item = c;
            }
        }
        return arr[b - 1];
    }

}
